#include <iostream>
#include <cassert>

using namespace std;

// 路径压缩 Quick Union + rank + path compression
namespace UF5{
	class UnionFind{
		private:
			int *parent;
			// rank[i]表示以i为根的集合所表示的树的层数
			int* rank;
			int count;
		public:
			UnionFind(int count){
				parent = new int[count];
				rank = new int[count];		// 开辟空间
				this->count = count;
				for(int i = 0; i < count; ++i){
					parent[i] = i;
					rank[i] = 1;				// 初始每个集合只有一个元素
				}
			}

			~UnionFind(){
				delete[] parent;
				delete[] rank;
			}

			int size(){
				return count;
			}

			// path compression
			int find(int p){
				assert(p >= 0 && p < count);
				while(p != parent[p]){
					parent[p] = parent[parent[p]];
					p = parent[p];
				}
				return p;
			}

			bool isConnected(int p, int q){
				return find(p) == find(q);
			}

			void unionElements(int p, int q){
			
				int pRoot = find(p);
				int qRoot = find(q);

				if(pRoot == qRoot){
					return;
				}
				
				// p 比  q层数低,则将p的父节点变为q
				if(rank[pRoot] < rank[qRoot]){	// rank 不需要维护
					parent[pRoot] = qRoot;
				}else if(rank[qRoot] < rank[pRoot]){
					parent[qRoot] = pRoot;
				}else{		// 两个rank 相等时
					parent[pRoot] = qRoot;
					rank[qRoot]++;
				}
			}

			void show(){
				for(int i = 0; i < count; ++i){
					cout << i << " : " << parent[i] << endl;
				}
			}
	};
}
